package alo.p3.work;


import alo.p3.ListNode;

import java.util.HashMap;

//判断给定的链表是以NULL结尾，还是形成一个环
public class DoesLinkedListContainsLoop {

    //使用散列表
    boolean DoesLinkedListContainsLoop(ListNode headNode) {
        ListNode currentNode = headNode;
        HashMap<ListNode, Boolean> map = new HashMap<>();
        //把头结点加入表中
        map.put(currentNode, true);
        //正常的链表结尾
        while (currentNode != null) {
            //逐个遍历链表的每个结点
            currentNode = currentNode.getNext();
            //如果访问过了，表面存在环,返回true
            if (map.containsKey(currentNode)) {
                return true;

            } else {//如果没有,加入表中
                map.put(currentNode, true);
            }
        }
        return false;
    }

    //Floyd环判定算法
    boolean DoesLinkedListContainsLoop2(ListNode headNode) {
        if (headNode == null) {
            return false;
        }
        ListNode slowPtr = headNode, fastPtr = headNode;
        while (fastPtr.getNext() != null && fastPtr.getNext().getNext() != null) {
            slowPtr = slowPtr.getNext();
            fastPtr = fastPtr.getNext().getNext();
            if (slowPtr == fastPtr)
                return true;
        }
        return false;
    }


    //判断给定的链表是否以NULL结束。如果链中存在环，找到环的起点
    ListNode FindBeginLoop(ListNode headNode) {
        ListNode slowPtr = headNode, fastPtr = headNode;
        boolean loopExists = false;
        if (headNode == null) {
            return null;
        }
        while (fastPtr.getNext() != null && slowPtr.getNext().getNext() != null) {
            slowPtr = slowPtr.getNext();
            fastPtr = fastPtr.getNext().getNext();
            if (slowPtr == fastPtr) {
                loopExists = true;
                break;
            }
        }
        if (loopExists) {
            slowPtr = headNode;
            while (slowPtr != fastPtr) {
                fastPtr = fastPtr.getNext();
                slowPtr = slowPtr.getNext();
            }
            return slowPtr;
        }
        return null;
    }


    //判断给定的链表是否以NULL结束。如果链中存在环，返回环的长度
    int FindLoopLength(ListNode headNode) {
        ListNode slowPtr = headNode, fastPtr = headNode;
        boolean loopExists = false;
        int counter = 0;
        if (headNode == null) {
            return 0;
        }
        while (fastPtr.getNext() != null && slowPtr.getNext().getNext() != null) {
            slowPtr = slowPtr.getNext();
            fastPtr = fastPtr.getNext().getNext();
            if (slowPtr == fastPtr) {
                loopExists = true;
                break;
            }
        }
        if (loopExists) {
            fastPtr = fastPtr.getNext();
            while (slowPtr != fastPtr) {
                fastPtr = fastPtr.getNext();
                counter++;
            }
            return counter;
        }
        return 0;
    }
}
